package 牛客算法篇;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-02-28
 * Time:15:37
 */

/**
 *
 牛客算法篇:NC86 矩阵元素查找
 已知一个有序矩阵mat，同时给定矩阵的大小n和m以及需要查找的元素x，且矩阵的行和列都是从小到大有序的。设计查找算法返回所查找元素的二元数组，代表该元素的行号和列号(均从零开始)。保证元素互异。
 数据范围：0≤n,m≤10000≤n,m≤1000，矩阵中的任何元素满足 0<mati,j≤10000000<mati,j​≤1000000
 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n+m)O(n+m)
 示例1
 输入：
 [[1,2,3],[4,5,6]],2,3,6
 返回值：
 [1,2]
 */
public class findElement {
    public static void main(String[] args) {
        findElement(new int[][]{{0,26,52},
                {1,27,53},
                {2,28,54},
                {3,29,55},
                {4,30,56},
                {5,31,57},
                {6,32,58},
                {7,33,59},
                {8,34,60},
        {9,35,61}},26,3,8);
    }
    public static int[] findElement (int[][] mat, int n, int m, int x) {
        // write code here
        int pow = 0;
        int col = m - 1;
        while(pow < n && col >= 0){
            if(mat[pow][col] < x){
                pow++;
            }else if(mat[pow][col] > x){
                col--;
            }else{
                break;
            }
        }
        return new int[]{pow,col};
    }
}
